#include "stdafx.h"
#include "__uintX2.h"

using namespace std;
typedef __uintX2<> uint128;

#define TEST_SMALL
#define TEST_LARGE
//#define MY_DEBUG
#define PRINT
int main()
{
#ifdef MY_DEBUG
	/** /
	uint128 a(8989324852324,1226562241422021),
            b(749137341425777760,146559513377350626);
	uint128::pow_m(a,b);

	cout<<count1<<endl;
	cout<<count2<<endl;
	//cout<<sizeof(uint128)<<endl;
    /** /
	for(int i=0;i<65;++i)
	{
		uint128 a(i);
		cout<<a<<"\t"<<a.weight()<<endl;
	}
	/** /
	for(int i=0;i<65;++i)
	{
		uint128 a(i);
		cout<<a<<"^(-1) = "<<a.inv(7)<<endl;
	}
	/**/
	uint128 b = 248, m = 1, mod = 772, a = 505, g = 2;
	for(int i=0;i<28;++i)
	{
		m = uint128::mult_m(m, b, mod);
		cout<<b<<" ^ "<<i+1<<" = "<<m<<"\t";
		a = uint128::mult_m(a, g, mod);
		cout<<"505 * "<<g<<" ^ "<<i+1<<" = "<<a<<"\n";
	}
	/**/
	return 0;
#endif /* MY_DEBUG */
	const usize_t TEST_SIZE=9;
#ifdef TEST_SMALL
	uint128 a_sm[TEST_SIZE]={51,78,36,12,55,10,21,5,71};
	uint128 b_sm[TEST_SIZE]={7,5,4,8,3,11,10,12,2};
#ifndef PRINT
	uint128 sum_sm[TEST_SIZE]={58,83,40,20,58,21,31,17,73};
	uint128 mult_sm[TEST_SIZE]={357,390,144,96,165,110,210,60,142};
	uint128 mod_sm[TEST_SIZE]={2,3,0,4,1,10,1,5,1};
	uint128 sqr_a_sm[TEST_SIZE]={2601,6084,1296,144,3025,100,441,25,5041};
	uint128 a_pow_b_sm[TEST_SIZE]={897410677851,2887174368,1679616,429981696,166375,100000000000,16679880978201,244140625,5041};
#else /* PRINT */
	cout<<"Small numbers test\n\n";
	cout<<"a\t"<<"b\t"<<"a+b\t"<<"ab\t"<<"a%b\t"<<"a/b\t"<<"a^2\t\t"<<"a^b\t\n";
#endif /* PRINT */
	for(usize_t i = 0;i<TEST_SIZE;++i)
	{
#ifdef PRINT
		cout<<a_sm[i]<<"\t"
			<<b_sm[i]<<"\t"
			<<a_sm[i]+b_sm[i]<<"\t"
			<<a_sm[i]*b_sm[i]<<"\t"
			<<a_sm[i]%b_sm[i]<<"\t"
			<<(a_sm[i]/b_sm[i])<<"\t"
			<<uint128::sqr_m(a_sm[i])<<"\t\t"
			<<uint128::pow_m(a_sm[i],b_sm[i],uint128(1,0))<<"\t\n";
#else /* PRINT */
		assert(a_sm[i]+b_sm[i]==sum_sm[i]);
		assert(a_sm[i]*b_sm[i]==mult_sm[i]);
		assert(a_sm[i]%b_sm[i]==mod_sm[i]);
		assert(uint128::sqr_m(a_sm[i])==sqr_a_sm[i]);
		assert(uint128::pow_m(a_sm[i],b_sm[i])==a_pow_b_sm[i]);
		cout<<'.';
#endif /* PRINT */
	}
#ifndef PRINT
	cout<<"Small numbers tests are passed!\n";
#endif /* PRINT */

#endif /* TEST_SMALL */
#ifdef TEST_LARGE
	uint128 a_lr[TEST_SIZE]={uint128(34359738368L,45035),
							 uint128(512,18446744073709551615),
							 uint128(4651324165,1556165165165),
							 uint128(8989324852324,0),
							 uint128(554122846533315,146550400854885050),
							 uint128(8542,8452018584),
							 uint128(185848542,68412412888),
							 /*uint128(887791306,56224142202),*/
							 uint128(1,1844674407375),
							 uint128(467073709551614,1)};
	uint128 b_lr[TEST_SIZE]={uint128(11529215,562949),
							 uint128(511,1),
							 uint128(4858854882463726,78541332185158452),
							 uint128(0,1226562241422021),
							 uint128(748583218579244445,9112522465576),
							 uint128(6884123321,0),
							 uint128(6884123321,559513377350),
							 /*uint128(699919274526581,291878877913063),*/
							 uint128(18446744073709551614,291878877913063),
							 uint128(56091452337071,100)};
	uint128 m_lr[TEST_SIZE]={uint128(1,510),
							 uint128(1,0),
							 uint128(454156,45646654651099456),
							 uint128(992855210300548881,0),
							 uint128(300548881, 992855210),
							 uint128(300548881, 0),
							 uint128(30039098548881,1520),
							 /*uint128(30029187887791306381,1132130015149877520UL),*/
							 uint128(100, 0),
							 uint128(1204, 698520)};
#ifndef PRINT
	uint128 sum_lr[TEST_SIZE]={uint128(34371267583,607984),
							   uint128(1024,0),
		                       uint128(4858859533787891,78542888350323617),
							   uint128(8989324852324,1226562241422021),
							   uint128(749137341425777760,146559513377350626),
							   uint128(6884131863,8452018584),
							   uint128(7069971863,627925790238),
							   /*uint128(699920162317887,291935102055265),*/
							   uint128(18446744073709551615,293723552320438),
							   uint128(523165161888685, 101)};
	uint128 mult_lr[TEST_SIZE]={uint128(1294203663747470435),
								uint128(18446744073709551615),
								uint128(359835,3669991927452658148),
								uint128(344562850575006849,0),
								uint128(24694436,14608925734601816514),
								uint128(4276586,0),
								uint128(17517588859265,15035313948088480208),
								/*uint128(15138388888363010630,3130807981446738870),*/
								uint128(24,14598205402907564233),
								uint128(545,16126752540207185164)};
	uint128 mod_lr[TEST_SIZE]={uint128(2677667,18446744072032008631),
							   uint128(1,18446744073709551614),
							   uint128(4651324165,1556165165165),
							   uint128(135424109458522),
							   uint128(554122846533315,146550400854885050),
							   uint128(8542,8452018584),
							   uint128(185848542,68412412888),
							   /*uint128(887791306,56224142202),*/
							   uint128(1,1844674407375),
							   uint128(18342090855045,18446744073709550817)};
	uint128 sqr_a_lr[TEST_SIZE]={uint128(16868405433497101751),
								 uint128(1),
								 uint128(350936,12351013009497868457),
								 uint128(542918788779130633,0),
								 uint128(80832899,6009750461050251716),
								 uint128(76306820,16096385923152710208),
								 uint128(9986356426635,537785510387700768),
								 /*uint128(12529055452848554420,5471699724163552772),*/
								 uint128(33,8130179327596441953),
								 uint128(210,3008638853380682193)};
	uint128 a_pow_b_lr[TEST_SIZE]={uint128(528072488794832589),
								   uint128(18446744073709551615),
								   uint128(121671,5586247898761727953),
								   uint128(93173857967455675,0),
								   uint128(251473001,4313213001514987700),
								   uint128(176239098,0),
								   uint128(14740036803368,13349282089952799472),
								   /*uint128(18106073380260734989,5072051649576642416),*/
								   uint128(60,297973091452337071),
								   uint128(21,6697860345537554609)};
#else /* PRINT */
	cout<<"\n\nLarge numbers test\n\n";
#endif /* PRINT */
	for(usize_t i = 0;i<TEST_SIZE;++i)
	{
#ifdef PRINT
		cout<<"a: "<<a_lr[i]<<"\t"
			<<"b: "<<b_lr[i]<<"\t"
			<<"m: "<<m_lr[i]<<"\t"
			<<"a+b: "<<a_lr[i]+b_lr[i]<<"\t"
			<<"a*b % m: "<<uint128::mult_m(a_lr[i],b_lr[i],m_lr[i])<<"\t"
			<<"a%b: "<<a_lr[i]%b_lr[i]<<"\t"
			<<"a^2 % m: "<<uint128::sqr_m(a_lr[i],m_lr[i])<<"\t"
			<<"a^b % m: "<<uint128::pow_m(a_lr[i],b_lr[i],m_lr[i])<<"\t\n"
			<<"-----------------------------------------------------\n";
#else /* PRINT */
		assert(a_lr[i]+b_lr[i]==sum_lr[i]);
		assert(uint128::mult_m(a_lr[i],b_lr[i],m_lr[i])==mult_lr[i]);
		assert(a_lr[i]%b_lr[i]==mod_lr[i]);
		assert(uint128::sqr_m(a_lr[i],m_lr[i])==sqr_a_lr[i]);
		assert(uint128::pow_m(a_lr[i],b_lr[i],m_lr[i])==a_pow_b_lr[i]);
		cout<<'.';
#endif /* PRINT */
	}
	
#ifndef PRINT
	cout<<"Large numbers tests are passed!\n";
#endif /* PRINT */

#endif /* TEST_LARGE */
	getchar();
	return 0;
}